#include <stdio.h>
#include <stdlib.h>
#include "huffman.h"

huff_tree thetree = {NULL, NULL, {NULL}, {NULL}, 0};

void huff_code_tostring (huff_code this) {
  int i;
  for (i = this->length - 1; i >= 0; i--) {
    putchar (((this->bits >> i) & 1L) ? '1' : '0');
  }
}

huff_node huff_node_new () {
  huff_node this = (huff_node) calloc (1, sizeof (struct huff_node_struct));
  return this;
}

void huff_node_init (huff_node this, int w, int c,
		     huff_node f, huff_node l, huff_node r, int i) {
  this->w = w; this->c = c; this->gdbh_index = i;
  this->father = f; this->left = l; this->right = r;
}

void huff_node_tostring (huff_node this) {
  printf ("[%c |%2d]", this->c ? this->c : '_', this->w);
}

void _huff_tree_tostring (huff_node n, int depth, long mask) {
  int i;
  for (i = 0; i < depth; i++) {
    if (mask & (1 << i)) {
      putchar (' ');  putchar ('|');
    }
    else {
      putchar (' ');
      putchar (' ');
    }
  }
  printf (" +--");
  huff_node_tostring (n);
  printf ("\n");
  if (n->left)
    _huff_tree_tostring (n->left, depth + 1, mask | (1 << (depth + 1)));
  if (n->right)
    _huff_tree_tostring (n->right, depth + 1, mask);
}

void huff_tree_tostring () {
  printf ("DynaHuff with %d nodes\n", thetree.count);
  _huff_tree_tostring (thetree.root, 0, 0L);
}

void huff_node_exchange (huff_node q, huff_node r) {
  int t; huff_node n;
  
  t = q->w; q->w = r->w; r->w = t;
  t = q->c; q->c = r->c; r->c = t;
  n = q->left; q->left = r->left; r->left = n;
  n = q->right; q->right = r->right; r->right = n;

  if (q->left) q->left->father = q;
  if (q->right) q->right->father = q;
  if (r->left) r->left->father = r;
  if (r->right) r->right->father = r;

  if (q->c != -1) thetree.chars[q->c] = q;
  if (r->c != -1) thetree.chars[r->c] = r;
}

int huff_node_isgdbh (huff_node this) {
  huff_node n;
  if (this->gdbh_index == 0)
    return 1;
  n = thetree.gdbh[this->gdbh_index - 1];
  return n->w > this->w;
}

huff_node huff_node_eob (huff_node this) {
  huff_node n = this;
  while (!huff_node_isgdbh (n))
    n = thetree.gdbh[n->gdbh_index - 1];
  
  if (n == this->father)
    return this;
  return n;
}

void huff_tree_update (huff_node q) {
  huff_node t, n = q;
  while (n) {
    t = huff_node_eob (n);
    if (t == n) {
      n->w++;
      n = n->father;
    } else {
      huff_node_exchange (n, t);
      n = t;
    }
  }
}

void huff_tree_modify (int c) {
  huff_node q;

  q = thetree.chars[c];
  if (!q) {
    huff_node new_special, n;
    new_special = huff_node_new ();
    n = huff_node_new ();

    huff_node_init (new_special, 1, -1,
		    thetree.special, NULL, n, thetree.count);
    thetree.gdbh[thetree.count++] = new_special;

    huff_node_init (n, 1, c, new_special,
		    NULL, NULL, thetree.count);
    thetree.gdbh[thetree.count++] = n;
    thetree.chars[c] = n;

    thetree.special->left = new_special;
    q = thetree.special;
    thetree.special = new_special;
  }
  huff_tree_update (q);  
}

void huff_node_get_code (huff_node this, huff_code res) {
  huff_node n = this, f = this->father;
  int length = 0, code = 0;

  while (f) {
    if (f->right == n)
      code |= 1 << length;
    length++;
    n = f;
    f = f->father;
  }
  res->length = length;
  res->bits = code;
}

void huff_tree_init (int c) {
  huff_node root = huff_node_new ();
  huff_node anode = huff_node_new ();

  huff_node_init (root, 1, -1, NULL, NULL, anode, 0);
  huff_node_init (anode, 1, c, root, NULL, NULL, 1);

  thetree.count = 2;
  thetree.root = root;
  thetree.special = root;
  thetree.gdbh[0] = root;
  thetree.gdbh[1] = anode;
  thetree.chars[c] = anode;
}

int huff_getcode (int c, huff_code res) {
  huff_node n = thetree.chars[c];
  if (!n) return 0;
  huff_node_get_code (n, res);
  return 1;
}

void huff_special_code (huff_code res) {
  huff_node n = thetree.special;
  huff_node_get_code (n, res);
  res->bits <<= 1;
  res->length++;
}

int huff_node_isspecial (huff_node this) {
  return (this->left == NULL) && (this->right != NULL);
}

int huff_node_isleaf (huff_node this) {
  return (this->left == NULL) && (this->right == NULL);
}
